#include "git-compat-util.h"
#include "string-list.h"

/**
 * Initializes a string list to not use strdup.
 * The strings added to the list will not be copied.
 *
 * @param list The string list to initialize.
 */
void string_list_init_nodup(struct string_list *list)
{
	struct string_list blank = STRING_LIST_INIT_NODUP;
	memcpy(list, &blank, sizeof(*list));
}

/**
 * Initializes a string list to use strdup.
 *
 * @param list The string list to initialize.
 */
void string_list_init_dup(struct string_list *list)
{
	struct string_list blank = STRING_LIST_INIT_DUP;
	memcpy(list, &blank, sizeof(*list));
}

/* if there is no exact match, point to the index where the entry could be
 * inserted */
/**
 * Searches for the given string in the string list, using the
 * list's compare function.
 *
 * Returns the index of the entry if found. Sets exact_match to 1 if
 * an exact match was found.
 *
 * If no exact match is found, returns the index where the entry could
 * be inserted, and sets exact_match to 0.
 */
static int get_entry_index(const struct string_list *list, const char *string,
		int *exact_match)
{
	int left = -1, right = list->nr;
	compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;

	while (left + 1 < right) {
		int middle = left + (right - left) / 2;
		int compare = cmp(string, list->items[middle].string);
		if (compare < 0)
			right = middle;
		else if (compare > 0)
			left = middle;
		else {
			*exact_match = 1;
			return middle;
		}
	}

	*exact_match = 0;
	return right;
}

/* returns -1-index if already exists */
/**
 * Adds an entry to the given string list.
 *
 * @param insert_at Index to insert at, or -1 to find index automatically.
 * @param list The string list to add to.
 * @param string The string to add.
 * @return The index the entry was added at, or -1 if it already existed.
 */
static int add_entry(int insert_at, struct string_list *list,
		     const char *string)
{
	int exact_match = 0;
	int index = insert_at != -1 ? insert_at : get_entry_index(list, string, &exact_match);

	if (exact_match)
		return -1 - index;

	ALLOC_GROW(list->items, list->nr+1, list->alloc);
	if (index < list->nr)
		MOVE_ARRAY(list->items + index + 1, list->items + index,
			   list->nr - index);
	list->items[index].string = list->strdup_strings ?
		xstrdup(string) : (char *)string;
	list->items[index].util = NULL;
	list->nr++;

	return index;
}

/**
 * Inserts the given string into the string list, maintaining sorted order.
 * Returns a pointer to the inserted string list item.
 */
struct string_list_item *string_list_insert(struct string_list *list,
					    const char *string)
{
	int index = add_entry(-1, list, string);

	if (index < 0)
		index = -1 - index;

	return list->items + index;
}

/**
 * Removes the given string from the string list if it exists.
 *
 * @param list The string list to remove from.
 * @param string The string to remove.
 * @param free_util If non-zero, free util field of the removed string.
 */
void string_list_remove(struct string_list *list, const char *string,
			int free_util)
{
	int exact_match;
	int i = get_entry_index(list, string, &exact_match);

	if (exact_match) {
		if (list->strdup_strings)
			free(list->items[i].string);
		if (free_util)
			free(list->items[i].util);

		list->nr--;
		MOVE_ARRAY(list->items + i, list->items + i + 1, list->nr - i);
	}
}

/**
 * Checks if the given string exists in the provided string list.
 *
 * @param list The string list to search.
 * @param string The string to look for.
 * @return 1 if the string was found, 0 otherwise.
 */
int string_list_has_string(const struct string_list *list, const char *string)
{
	int exact_match;
	get_entry_index(list, string, &exact_match);
	return exact_match;
}

/**
 * Finds the index where the given string should be inserted in the
 * string list to maintain sorted order. Returns a negative integer if the
 * string already exists in the list as an exact match.
 */
int string_list_find_insert_index(const struct string_list *list,
				  const char *string,
				  int negative_existing_index)
{
	int exact_match;
	int index = get_entry_index(list, string, &exact_match);
	if (exact_match)
		index = -1 - (negative_existing_index ? index : 0);
	return index;
}

/**
 * Looks up an entry by string in the given string list.
 *
 * @param list The string list to search.
 * @param string The string to look up.
 * @return A pointer to the string list item if found, NULL if not found.
 */
struct string_list_item *string_list_lookup(struct string_list *list,
					    const char *string)
{
	int exact_match, i = get_entry_index(list, string, &exact_match);
	if (!exact_match)
		return NULL;
	return list->items + i;
}

/**
 * Removes duplicate entries from the given string list by comparing
 * strings using strcmp().
 *
 * If free_util is non-zero, also frees the util field of
 * removed items.
 */
void string_list_remove_duplicates(struct string_list *list, int free_util)
{
	if (list->nr > 1) {
		int src, dst;
		compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
		for (src = dst = 1; src < list->nr; src++) {
			if (!cmp(list->items[dst - 1].string, list->items[src].string)) {
				if (list->strdup_strings)
					free(list->items[src].string);
				if (free_util)
					free(list->items[src].util);
			} else
				list->items[dst++] = list->items[src];
		}
		list->nr = dst;
	}
}

/**
 * Iterates over each string in the given string list,
 * calling the given callback function on each. Stops
 * and returns the callback return value if the callback
 * returns a non-zero value.
 */
int for_each_string_list(struct string_list *list,
			 string_list_each_func_t fn, void *cb_data)
{
	int i, ret = 0;
	for (i = 0; i < list->nr; i++)
		if ((ret = fn(&list->items[i], cb_data)))
			break;
	return ret;
}

/**
 * Filters the given string list by removing items based on
 * the given predicate function.
 *
 * @param list The string list to filter.
 * @param free_util If non-zero, free the util field of
 *                  removed items.
 * @param want The predicate function to determine which
 *             items to keep.
 * @param data Opaque data passed to the predicate function.
 */
void filter_string_list(struct string_list *list, int free_util,
			string_list_each_func_t want, void *cb_data)
{
	int src, dst = 0;
	for (src = 0; src < list->nr; src++) {
		if (want(&list->items[src], cb_data)) {
			list->items[dst++] = list->items[src];
		} else {
			if (list->strdup_strings)
				free(list->items[src].string);
			if (free_util)
				free(list->items[src].util);
		}
	}
	list->nr = dst;
}

/**
 * Checks if the given string list item's string is not empty.
 *
 * @param item The string list item to check.
 * @param data Unused parameter.
 * @return 1 if the item's string is not empty, 0 otherwise.
 */
static int item_is_not_empty(struct string_list_item *item, void *data UNUSED)
{
	return *item->string != '\0';
}

/**
 * Removes empty strings from the given string list.
 *
 * @param list The string list to remove empty strings from.
 * @param free_util If non-zero, free the util field of the removed items.
 */
void string_list_remove_empty_items(struct string_list *list, int free_util)
{
	filter_string_list(list, free_util, item_is_not_empty, NULL);
}

/**
 * Clears the given string list, freeing all memory associated with
 * it. If free_util is non-zero, the util field of each item is
 * freed via a call to free().
 */
void string_list_clear(struct string_list *list, int free_util)
{
	if (list->items) {
		int i;
		if (list->strdup_strings) {
			for (i = 0; i < list->nr; i++)
				free(list->items[i].string);
		}
		if (free_util) {
			for (i = 0; i < list->nr; i++)
				free(list->items[i].util);
		}
		free(list->items);
	}
	list->items = NULL;
	list->nr = list->alloc = 0;
}

/**
 * Clears the given string list, calling the given clearfunc
 * callback function on each existing item's util field and
 * string field before freeing the item.
 *
 * @param list The string list to clear.
 * @param clearfunc The callback function to call on each item.
 */
void string_list_clear_func(struct string_list *list,
			    string_list_clear_func_t clearfunc)
{
	if (list->items) {
		int i;
		if (clearfunc) {
			for (i = 0; i < list->nr; i++)
				clearfunc(list->items[i].util, list->items[i].string);
		}
		if (list->strdup_strings) {
			for (i = 0; i < list->nr; i++)
				free(list->items[i].string);
		}
		free(list->items);
	}
	list->items = NULL;
	list->nr = list->alloc = 0;
}

/**
 * Sets the length of the given string list.
 *
 * @param list The string list to set the length of.
 * @param nr The new length for the list. Must be <= the current length.
 */
void string_list_setlen(struct string_list *list, size_t nr)
{
	if (list->strdup_strings)
		BUG("cannot setlen a string_list which owns its entries");
	if (nr > list->nr)
		BUG("cannot grow a string_list with setlen");
	list->nr = nr;
}

/**
 * Appends a new string to the given string list without duplicating the string.
 * Allocates a new string_list_item to hold the string.
 */
struct string_list_item *string_list_append_nodup(struct string_list *list,
						  char *string)
{
	struct string_list_item *retval;
	ALLOC_GROW(list->items, list->nr + 1, list->alloc);
	retval = &list->items[list->nr++];
	retval->string = string;
	retval->util = NULL;
	return retval;
}

/**
 * Appends a string to the given string list, allocating a new
 * string_list_item to hold it. Handles string duplication if
 * configured.
 */
struct string_list_item *string_list_append(struct string_list *list,
					    const char *string)
{
	return string_list_append_nodup(
			list,
			list->strdup_strings ? xstrdup(string) : (char *)string);
}

/*
 * Encapsulate the compare function pointer because ISO C99 forbids
 * casting from void * to a function pointer and vice versa.
 */
struct string_list_sort_ctx
{
	compare_strings_fn cmp;
};

/**
 * Compare two string list items for sorting.
 *
 * This is passed as the comparison function to qsort() when
 * sorting the string list. It receives pointers to two
 * string_list_item structs and calls the configured string
 * comparison function on the strings.
 */
static int cmp_items(const void *a, const void *b, void *ctx)
{
	struct string_list_sort_ctx *sort_ctx = ctx;
	const struct string_list_item *one = a;
	const struct string_list_item *two = b;
	return sort_ctx->cmp(one->string, two->string);
}

/**
 * Sorts the given string list in place. Uses the compare function
 * provided in the list struct if available, otherwise strcmp.
 */
void string_list_sort(struct string_list *list)
{
	struct string_list_sort_ctx sort_ctx = {list->cmp ? list->cmp : strcmp};

	QSORT_S(list->items, list->nr, cmp_items, &sort_ctx);
}

/**
 * Looks up the given string in the unsorted string list and returns the
 * corresponding string list item if found. Returns NULL if not found.
 */
struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
						     const char *string)
{
	struct string_list_item *item;
	compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;

	for_each_string_list_item(item, list)
		if (!cmp(string, item->string))
			return item;
	return NULL;
}

/**
 * Checks if the given string exists in the unsorted string list.
 *
 * @param list The string list to check.
 * @param string The string to look for.
 * @return Non-zero if the string was found, zero otherwise.
 */
int unsorted_string_list_has_string(struct string_list *list,
				    const char *string)
{
	return unsorted_string_list_lookup(list, string) != NULL;
}

/**
 * Deletes the item at the specified index from the given unsorted
 * string list.
 *
 * @param list The string list.
 * @param i The index of the item to delete.
 * @param free_util If non-zero, free any util field.
 */
void unsorted_string_list_delete_item(struct string_list *list, int i,
				      int free_util)
{
	if (list->strdup_strings)
		free(list->items[i].string);
	if (free_util)
		free(list->items[i].util);
	list->items[i] = list->items[list->nr-1];
	list->nr--;
}

/**
 * Splits the given string into items separated by the given delimiter
 * character(s) and appends them to the given string list.
 *
 * @param list The string list to append the split string items to.
 * @param string The string to split.
 * @param delim The delimiter character(s).
 */
int string_list_split(struct string_list *list, const char *string,
		      int delim, int maxsplit)
{
	int count = 0;
	const char *p = string, *end;

	if (!list->strdup_strings)
		die("internal error in string_list_split(): "
		    "list->strdup_strings must be set");
	for (;;) {
		count++;
		if (maxsplit >= 0 && count > maxsplit) {
			string_list_append(list, p);
			return count;
		}
		end = strchr(p, delim);
		if (end) {
			string_list_append_nodup(list, xmemdupz(p, end - p));
			p = end + 1;
		} else {
			string_list_append(list, p);
			return count;
		}
	}
}

/**
 * Splits the given string in-place using the specified delimiter.
 *
 * Modifies the string in-place by replacing delimiter characters with null
 * terminators. The substrings between delimiters are then appended as
 * individual items to the given string list.
 *
 * @param list The string list to append split string items to.
 * @param string The string to split. This will be modified in-place.
 * @param delim The delimiter character(s) to split on.
 * @param maxsplit Maximum number of splits. Negative for unlimited.
 * @return The number of splits performed.
 */
int string_list_split_in_place(struct string_list *list, char *string,
			       const char *delim, int maxsplit)
{
	int count = 0;
	char *p = string, *end;

	if (list->strdup_strings)
		die("internal error in string_list_split_in_place(): "
		    "list->strdup_strings must not be set");
	for (;;) {
		count++;
		if (maxsplit >= 0 && count > maxsplit) {
			string_list_append(list, p);
			return count;
		}
		end = strpbrk(p, delim);
		if (end) {
			*end = '\0';
			string_list_append(list, p);
			p = end + 1;
		} else {
			string_list_append(list, p);
			return count;
		}
	}
}
